(* mySet.mli *)
 
(* Signature des elements *)
module type OrderedType =
sig
  type t
  val compare: t -> t -> int
end
 
(* Signature du resultat du foncteur *)
module type S =
sig
  type elm
  type t
  val empty : t
    (* ensemble vide *)
  val is_empty: t -> bool
    (* test du vide *)
  val cardinal: t -> int
    (* taille de l'ensemble *)
  val mem: elm -> t -> bool
    (* test d'appartenance *)
  val sub: t -> t -> bool
    (*
     * sub s1 s2 renvoie vrai si tous les elements de s1 sont dans s2
     *)
 
  val add: elm -> t -> t
    (*
     * add x s renvoie un nouvel ensemble contenant tous les elements
     * de s et x.
     * invariant: si s est trie sans doublon alors (add x s) est trie
     * sans doublon.
     * post-condition: mem x (add x s) renvoie vrai
     * post-condition: 0 <= (cardinal (add x s)) - (cardinal s) <= 1
     *)
 
  val union: t -> t -> t
    (*
     * union s1 s2 renvoie un nouvel ensemble contenant tous les
     * elements de s1 et tous les elements de s2.
     * invariant: si s1 et s2 sont tries sans doublon
     *            alors (union s1 s2) est trie sans doublon.
     * post-condition:
     *   cardinal (union s1 s2) <= cardinal s1 + cardinal s2
     *)
 
  val iter: (elm -> unit) -> t -> unit
    (*
     * iter f s applique la fonction f a tous les elements de s
     * les elements sont presentes dans l'ordre.
     *)
 
end
 
(* le foncteur *)
module Make : functor (T : OrderedType) -> S with type elm = T.t
